package com.gorkr.labuladong.data_struct.bt;

import org.junit.jupiter.api.Test;

/**
 * 前序中序 构造二叉树
 *
 * @author gorkr
 * @date 2022/07/25 19:43
 **/
public class M7ChongJianErChaShuIcof {
    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder,  0, preorder.length - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder,  int left, int right) {
        if (left > right || index > preorder.length) {
            return null;
        }

        int val = preorder[index];
        index++;
        TreeNode root = new TreeNode(val);
        int i;
        for (i = left; i <= right; i++) {
            if (inorder[i] == val) {
                break;
            }
        }
//        index++;
        root.left = build(preorder, inorder,  left, i - 1);
//        index++;
        root.right = build(preorder, inorder,  i + 1, right);
        return root;
    }


    @Test
    public void test() {
        int[] preorder = {1,2};
        int[] inorder = {1,2};

//        int[] preorder = {3,9,20,15,7};
//        int[] inorder = {9,3,15,20,7};

        TreeNode treeNode = buildTree(preorder, inorder);
        System.out.println(treeNode.toString());
    }

}
    